Drukarka
Limit pamięci: 64 MB
Musisz wydrukować słów.
Twoja drukarka to stary model, który obsługuje się, składając słowo z czcionek - odlanych z metalu małych elementów,
z których każdy zawiera jedną literę. Do tak ułożonego wzoru przykłada się kartkę papieru, aby wydrukować złożone słowo.
Drukarka, którą posiadasz, pozwala na wykonanie każdej z następujących operacji:
- dodania jednej litery na końcu słowa znajdującego się aktualnie w drukarce;
- usunięcia ostatniej litery słowa znajdującego się aktualnie w drukarce;
- wydrukowania słowa znajdującego się aktualnie w drukarce.
Początkowo drukarka jest pusta; nie zawiera żadnych czcionek.
Po zakończeniu pracy nie musisz czyścić drukarki - możesz pozostawić w niej dowolne czcionki.
Ponadto, słowa możesz drukować w dowolnej kolejności.
Ponieważ każda z operacji wymaga pewnego czasu, chcesz zminimalizować łączną liczbę wykonanych operacji.
Zadanie
Napisz program, który mając danych słów, wyznaczy minimalną
liczbę operacji potrzebnych do ich wydrukowania w dowolnej kolejności
i wypisze jedną taką sekwencję operacji.
Ograniczenia
- liczba słów, które chcesz wydrukować.
Wejście
Twój program powinien wczytać ze standardowego wejścia następujące dane:
- Pierwszy wiersz zawierający liczbę całkowitą - liczbę słów do wydrukowania.
- Kolejnych wierszy, z których każdy zawiera jedno słowo.
Każde słowo składa się wyłącznie z małych liter ('a' - 'z') i ma długość od 1 do 20 (włącznie).
Wszystkie słowa są różne.
Wyjście
Twój program powinien wypisać na standardowe wyjście następujący wynik:
- Pierwszy wiersz powinien zawierać liczbę całkowitą oznaczającą minimalną
liczbę operacji potrzebnych do wydrukowania danych słów.
- Każdy z kolejnych wierszy powinien zawierać jeden znak.
Znaki te opisują sekwencję wykonanych operacji.
Każda z nich musi być zapisana następująco:
- dodanie małej litery jest reprezentowane przez nią samą,
- usunięcie ostatniej litery jest reprezentowane przez znak '-' (minus, kod ASCII 45),
- wydrukowanie aktualnego słowa jest reprezentowane przez znak 'P' (wielka litera P).
Punktacja
W testach wartych łącznie 40 punktów, wartość nie przekracza 18.
Przykład
Dla danych wejściowych:
3
print
the
poem
poprawną odpowiedzią jest:
20
t
h
e
P
-
-
-
p
o
e
m
P
-
-
-
r
i
n
t
P